package com.jiangli.utils.Sreach;

public class EditDistanceUtils {

    /**
     * 计算两个字符串的编辑距离
     * @param s1 源字符串
     * @param s2 目标字符串
     * @return 编辑距离（值越小越相似）
     */
    public static int calculateEditDistance(String s1, String s2) {
        if (s1 == null || s2 == null) {
            return 0;
        }

        int len1 = s1.length();
        int len2 = s2.length();

        // 创建dp数组，dp[i][j]表示s1前i个字符与s2前j个字符的编辑距离
        int[][] dp = new int[len1 + 1][len2 + 1];

        // 初始化边界：空字符串到目标字符串的距离
        for (int i = 0; i <= len1; i++) {
            dp[i][0] = i;
        }
        for (int j = 0; j <= len2; j++) {
            dp[0][j] = j;
        }

        // 填充dp数组
        for (int i = 1; i <= len1; i++) {
            char c1 = s1.charAt(i - 1);
            for (int j = 1; j <= len2; j++) {
                char c2 = s2.charAt(j - 1);

                if (c1 == c2) {
                    // 字符相同，距离等于前一个状态
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    // 取三种操作的最小值+1
                    int insert = dp[i][j - 1] + 1;       // 插入
                    int delete = dp[i - 1][j] + 1;       // 删除
                    int replace = dp[i - 1][j - 1] + 1;  // 替换
                    dp[i][j] = Math.min(Math.min(insert, delete), replace);
                }
            }
        }

        return dp[len1][len2];
    }

    /**
     * 计算字符串相似度
     * @param s1 源字符串
     * @param s2 目标字符串
     * @return 相似度（0-1之间，值越大越相似）
     */
    public static double calculateSimilarity(String s1, String s2) {
        if (s1 == null || s2 == null) {
            return 0.0;
        }
        int maxLen = Math.max(s1.length(), s2.length());
        if (maxLen == 0) {
            return 1.0;
        }
        return 1.0 - (double) calculateEditDistance(s1, s2) / maxLen;
    }

    /**
     * 判断两个字符串是否相似
     * @param s1 源字符串
     * @param s2 目标字符串
     * @param threshold 相似度阈值
     * @return 是否相似
     */
    public static boolean isSimilar(String s1, String s2, double threshold) {
        return calculateSimilarity(s1, s2) >= threshold;
    }
}